package basic.courseLearn03.heap;

import basic.utils.CommonUtil;

public class RelateOperate {

    private static int heapTop=0;

    //初始化堆
    public static int[] initHeap_one(int[] arr){
        heapTop=0;
        for (int i = 0; i < arr.length; i++) {
            heapUp(arr,i);
            heapTop++;
        }
        heapTop-=1;
        return arr;
    }

    //向上调整，一直和父节点进行比较
    public static int[] heapUp(int[] arr,int index){
        if(index>heapTop){
            return new int[]{};
        }
        while(true){
            if (arr[index]>arr[(index-1)/2]){
                CommonUtil.swap(arr,index,(index-1)/2);
            }else {
                break;
            }
            index=(index-1)/2;
        }
        return arr;
    }

    //向下调整
    public static int[] heapDown(int[] arr,int index){
        if(index>heapTop){
            return new int[]{};
        }
        while(true){
            int max=0,maxIndex=0;
            if (2*index+2<=heapTop){      //有左，有右
                max=(arr[2*index+2]>arr[2*index+1])?arr[2*index+2]:arr[2*index+1];
                maxIndex=(arr[2*index+2]>arr[2*index+1])?2*index+2:2*index+1;
            }
            if (2*index+1<=heapTop && 2*index+2 > heapTop){      //有左，无右
                max=arr[2*index+1];
                maxIndex=2*index+1;
            }
            if (2*index+1 > heapTop){       //无左，无右
                break;
            }

            if (arr[index] < max){      //需要交换
                CommonUtil.swap(arr,index,maxIndex);
            }else {
                break;
            }
            index=maxIndex;
        }
        return arr;
    }


    //修改值
    public static int[] heapUpdate(int[] arr, int index,int x){
        arr[index]=x;
        arr=heapUp(arr,index);
        arr=heapDown(arr,index);
        return arr;
    }


    //输出
    public static int push(int[] arr){
        int result = arr[0];
        arr[0]=arr[heapTop];
        heapTop--;
        arr=heapDown(arr,0);
        return result;

    }





}
